/*
 * @lc app=leetcode.cn id=56 lang=java
 *
 * [56] 合并区间
 */

// @lc code=start

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> ans = new ArrayList<>();

        
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
            }
        });

        int[] pre = intervals[0];
        int[] cur = null;

        for(int i=1;i<intervals.length;i++){
            cur = intervals[i];
            if(pre[1] < cur[0]){
                ans.add(new int[]{pre[0], pre[1]});
                pre = cur;
                cur = null;
            } else if(pre[1] >= cur[0] && pre[1] <= cur[1]){
                pre[1] = cur[1];
                cur = null;
            }
        }
        ans.add(pre);
        return ans.toArray(new int[ans.size()][]);
    }

}
// @lc code=end

